package com.gitee.swsk33.algorithms.search;

import com.gitee.swsk33.algorithms.tree.binarytree.BinaryTree;
import com.gitee.swsk33.algorithms.tree.binarytree.TreeNode;

/**
 * 二叉排序树的实用类
 */
public class BinarySortTree {

	/**
	 * 二叉排序树查找
	 *
	 * @param treeRoot 待查找的排序树的根节点
	 * @param value    待查找结点值
	 * @return 如果查找到值等于待查找值的结点，则返回该结点；如果树中没有该结点为指定值，则返回最后一个被查找（被比较）到的结点
	 */
	public static TreeNode<Integer> searchNode(TreeNode<Integer> treeRoot, int value) {
		// 如果当前结点值等于给定值则返回当前结点
		if (treeRoot.getData() == value) {
			return treeRoot;
		} else if (value > treeRoot.getData() && treeRoot.getRight() != null) {
			// 如果给定值大于当前结点，则递归查找右子树
			return searchNode(treeRoot.getRight(), value);
		} else if (value < treeRoot.getData() && treeRoot.getLeft() != null) {
			// 如果给定值小于当前结点，则递归查找左子树
			return searchNode(treeRoot.getLeft(), value);
		}
		// 到这里说明被查找结点不存在，就返回最后被比较的结点
		return treeRoot;
	}

	/**
	 * 向二叉排序树插入一个结点
	 *
	 * @param tree  待插入结点的树
	 * @param value 待插入的结点
	 */
	public static void insertNode(BinaryTree<Integer> tree, int value) {
		// 当前被比较结点，从根结点开始往下索引
		TreeNode<Integer> current = searchNode(tree.getRoot(), value);
		// 如果当前遍历的集合值小于当前索引到树的结点值，则把当前值作为当前索引到结点的左孩子，否则作为右孩子
		TreeNode<Integer> insertNode = new TreeNode<>(value);
		if (value < current.getData()) {
			current.setLeft(insertNode);
			insertNode.setParent(current);
		} else if (value > current.getData()) {
			current.setRight(insertNode);
			insertNode.setParent(current);
		}
		// 相等则不作任何操作
	}

	/**
	 * 从二叉排序树中删除一个结点
	 *
	 * @param tree  待删除结点的二叉排序树
	 * @param value 待删除的值
	 */
	public static void deleteNode(BinaryTree<Integer> tree, int value) {
		// 先索引至被删除的结点的引用
		TreeNode<Integer> current = searchNode(tree.getRoot(), value);
		// 若当前索引节点与给定值不符说明给定值不存在，返回
		if (current.getData() != value) {
			return;
		}
		// 左子树为空则重接其右子树
		if (current.getLeft() == null) {
			// 判断自身是其双亲结点的左子树还是右子树
			if (current == current.getParent().getLeft()) {
				current.getParent().setLeft(current.getRight());
			} else {
				current.getParent().setRight(current.getRight());
			}
			current.setParent(null);
		} else if (current.getRight() == null) {
			// 右子树为空则重接其左子树
			// 判断自身是其双亲结点的左子树还是右子树
			if (current == current.getParent().getLeft()) {
				current.getParent().setLeft(current.getLeft());
			} else {
				current.getParent().setRight(current.getLeft());
			}
			current.setParent(null);
		} else {
			// 左右子树都不空
			// 先索引到其左子树最大的结点
			TreeNode<Integer> leftMax = current.getLeft();
			while (leftMax.getRight() != null) {
				leftMax = leftMax.getRight();
			}
			// 令被删除结点的值域等于左子树最大结点
			current.setData(leftMax.getData());
			// 然后删除左子树最大结点（这个结点只会是存在左子树或者右子树之一，不可能左右子树同时存在）
			// 还是上面的判断逻辑
			if (leftMax.getLeft() == null) {
				if (leftMax == leftMax.getParent().getLeft()) {
					leftMax.getParent().setLeft(leftMax.getRight());
				} else {
					leftMax.getParent().setRight(leftMax.getRight());
				}
			} else if (leftMax.getRight() == null) {
				if (leftMax == leftMax.getParent().getLeft()) {
					leftMax.getParent().setLeft(leftMax.getLeft());
				} else {
					leftMax.getParent().setRight(leftMax.getLeft());
				}
			}
			leftMax.setParent(null);
		}
	}

	/**
	 * 把一个无序整数集合构造成二叉排序树
	 *
	 * @param originList 原始无序整数集合
	 * @return 构造的二叉排序树
	 */
	public static BinaryTree<Integer> createSortTree(int[] originList) {
		// 把集合中的第一个元素作为二叉排序树的根结点
		BinaryTree<Integer> tree = new BinaryTree<>(originList[0]);
		// 遍历集合开始插入，从第2个开始
		for (int i = 1; i < originList.length; i++) {
			insertNode(tree, originList[i]);
		}
		return tree;
	}

}